
#include <errno.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>

#include "apr-1/apr_lib.h"
#include "apr-1/apr_errno.h"
#include "apr-1/apr_pools.h"
#include "apr-1/apr_general.h"
#include "apr-1/apr_file_io.h"
#include "apr-1/apr_file_info.h"

#include "map.h"
/*------------------------------------------------------------------------*/
#define ROOT_DIR	"."
/*------------------------------------------------------------------------*/
extern apr_pool_t *gpool;
/*------------------------------------------------------------------------*/

#pragma pack(1)

typedef struct _map2_item_pin {
	uint8_t check_sum;
	uint8_t flag;
	uint32_t index;
	uint8_t klen;
	uint8_t kval[4];	
}map2_item_pin_t;
#pragma pack()

static uint32_t map2_item_size(const map2_item_t* item){
	uint32_t size = sizeof(*item);
	size += item->klen;
	return size;
}

static uint8_t map2_item_get_check_sum(const map2_item_t* item){
	const uint32_t len = map2_item_size(item) - 1;
	const uint8_t *p = &item->flag;
	uint8_t check_sum = 0;
	
	for(uint32_t i = 0; i < len; i++){
		check_sum += p[i];
	}

	return ~ check_sum;
}

static int map2_item_verify(const map2_item_t* item){
	if(!(item->flag & 0x01)){
		return 0;
	}
	
	uint8_t check_sum = map2_item_get_check_sum(item);
	if(check_sum != item->check_sum){
		return 0;
	}

	return 1;
}

map2_item_t* map2_item_build_static(uint8_t *buf, const void* key_data, uint8_t key_size, uint32_t index){
	size_t xWantedSize = sizeof(map2_item_t)+key_size;
	map2_item_t* item = (map2_item_t* )buf;
	memset(item, 0, xWantedSize);
	item->index = index;
	if(key_data){
		memcpy(item->kval, key_data, key_size);
	}
	item->klen = key_size;
	return item;
}


static int map2_item_cmp(const map2_item_t *a1, const map2_item_t *a2){
	const void* k1 = a1->kval;
	const void* k2 = a2->kval;
	int len = a1->klen;
    return memcmp(k1, k2, len);
}

static void map2_item_copy(map2_item_t *dest, const map2_item_t *src){
    *dest = *src;
    memcpy(dest->kval, src->kval, src->klen);
}

#define MAP2_ITEM_ARR(arr, size, idx)		(map2_item_t *)((uint8_t*)(arr) + (size) * (idx))

//sort
void map2_item_sort(map2_item_t *a, int len)
{
    uint8_t buf[64];
    int i, j, k, gap;  // gap 为步长
    map2_item_t* tmp = (map2_item_t*)buf;
	size_t size = map2_item_size(a);
	uint8_t* arr = (uint8_t*)a;

    for (gap = len / 2; gap > 0; gap /= 2) {  // 步长初始化为数组长度的一半，每次遍历后步长减半,
    	for (i = 0; i < gap; ++i) { // 变量 i 为每次分组的第一个元素下标 
	        for (j = i + gap; j < len; j += gap) { //对步长为gap的元素进行直插排序，当gap为1时，就是直插排序
	            // 备份a[j]的值
                map2_item_copy(tmp, MAP2_ITEM_ARR(arr, size, j));
	            k = j - gap;  // k初始化为i的前一个元素（与i相差gap长度）
	            while (k >= 0 && map2_item_cmp(MAP2_ITEM_ARR(arr, size, k), tmp) > 0) {
	                // 将在a[i]前且比tmp的值大的元素向后移动一位
                    map2_item_copy(MAP2_ITEM_ARR(arr, size, k + gap), MAP2_ITEM_ARR(arr, size, k));
	                k -= gap;
	            }
	            // a[k + gap] = tmp; 
                map2_item_copy(MAP2_ITEM_ARR(arr, size, k + gap), tmp);
	        }
	    }
    }
}


map2_item_pin_t test_items[10];

void test_sort(void){
	uint32_t pins[10];
	uint32_t n = 10;

	for(int i = 0; i < 10; i++){
		pins[i] = n--;
	}

	for(int i = 0; i < 10; i++){
		test_items[i].index = i;
		test_items[i].klen = 4;
		memcpy(test_items[i].kval, &pins[i], 4);
	}

	map2_item_sort((map2_item_t*)test_items, 10);
}

/*============================================================================================================*/
enum {
	FR_OK = 0,				/* (0) Succeeded */
	FR_DISK_ERR,			/* (1) A hard error occurred in the low level disk I/O layer */
	FR_INT_ERR,				/* (2) Assertion failed */
	FR_NOT_READY,			/* (3) The physical drive cannot work */
	FR_NO_FILE,				/* (4) Could not find the file */
	FR_NO_PATH,				/* (5) Could not find the path */
	FR_INVALID_NAME,		/* (6) The path name format is invalid */
	FR_DENIED,				/* (7) Access denied due to prohibited access or directory full */
	FR_EXIST,				/* (8) Access denied due to prohibited access */
	FR_INVALID_OBJECT,		/* (9) The file/directory object is invalid */
	FR_WRITE_PROTECTED,		/* (10) The physical drive is write protected */
	FR_INVALID_DRIVE,		/* (11) The logical drive number is invalid */
	FR_NOT_ENABLED,			/* (12) The volume has no work area */
	FR_NO_FILESYSTEM,		/* (13) There is no valid FAT volume */
	FR_MKFS_ABORTED,		/* (14) The f_mkfs() aborted due to any problem */
	FR_TIMEOUT,				/* (15) Could not get a grant to access the volume within defined period */
	FR_LOCKED,				/* (16) The operation is rejected according to the file sharing policy */
	FR_NOT_ENOUGH_CORE,		/* (17) LFN working buffer could not be allocated */
	FR_TOO_MANY_OPEN_FILES,	/* (18) Number of open files > FF_FS_LOCK */
	FR_INVALID_PARAMETER	/* (19) Given parameter is invalid */
} ;

#define TRACE_E					printf
#define f_lseek(fp, pos)		fseek(fp, pos, SEEK_SET)
#define f_tell(fp)				ftell(fp)
#define f_close(fp)				fclose(fp)
#define f_eof(fp)				feof(fp)
#define FRESULT					int
#define UINT					unsigned int



int f_size(FIL* fp){
	fseek(fp, 0, SEEK_END);
	return ftell(fp);
}

int map2_f_is_openning(FIL* fp){
	if(fp && f_lseek(fp, f_tell(fp)) == FR_OK){
		return 1;
	}
	return 0;
}

int map2_f_open(FIL** fp, const char* path){
	if(*fp && f_lseek(*fp, f_tell(*fp)) == FR_OK){
		return 0;
	}
	*fp = fopen( path, "r+b");
	if(*fp){
		return 0;
	}
	*fp = fopen(path, "w+b");
	if(*fp){
		return 0;
	}	
	TRACE_E("open %s fail: %d\n", path, errno);
	return - errno;
}

int map2_f_close(FIL** fp){
	if(fp && *fp){
		f_close(*fp);
		*fp = NULL;
	}
	return 0;
}

int map2_f_get(FIL* fp, uint32_t size, map2_item_t* item){
	// UINT br;
	
	while(1){
		// br = 0;
		// FRESULT res = f_read(fp, item, size, &br);
		// if(res != FR_OK || br != size){
		// 	return -EIO;
		// }
		int rlen = fread(item, 1, size, fp);
		if(rlen != size){
			return -ENODATA;
		}
		if(map2_item_verify(item)){
			break;
		}
	}
	
	return 0;
}

int map2_f_read(FIL* fp, uint32_t index, uint32_t size, map2_item_t* item){
	if(f_lseek(fp, index * size)){
		return -ENOENT;
	}
	// UINT br = 0;
	// FRESULT res = f_read(fp, item, size, &br);
	// if(res != FR_OK || br != size){
	// 	return -EIO;
	// }
	int rlen = fread(item, 1, size, fp);
	if(rlen != size){
		return -ENODATA;
	}
	return 0;
}

int map2_f_write(FIL* fp, uint32_t index, map2_item_t* item){
	uint32_t size = map2_item_size(item);
	if(f_lseek(fp, index * size)){
		return -ENOENT;
	}

	// UINT bw = 0;
	// FRESULT res = f_write(fp, item, size, &bw);
	// if(res != FR_OK || bw != size){
	// 	return -EIO;
	// }
	int wlen = fwrite(item, 1, size, fp);
	if(wlen != size){
		return -EIO;
	}
	return 0;
}

/*----------------------------------------------------------------------*/

int map2_f_delete(FIL* fp, uint32_t index, map2_item_t* item){
	uint32_t size = map2_item_size(item);
	if(f_lseek(fp, index * size)){
		return -ENOENT;
	}
	item->flag = 0;
	item->check_sum = map2_item_get_check_sum(item);
	// UINT bw = 0;
	// FRESULT res = f_write(fp, item, size, &bw);
	// if(res != FR_OK || bw != size){
	// 	return -EIO;
	// }
	int wlen = fwrite(item, 1, size, fp);
	if(wlen != size){
		return -EIO;
	}
	return 0;
}

int map2_f_update(FIL* fp, uint32_t index, map2_item_t* item){
	item->flag = 1;
	item->check_sum = map2_item_get_check_sum(item);
	return map2_f_write(fp, index, item);
}

int map2_f_append(FIL* fp, map2_item_t* item){
	uint32_t size = map2_item_size(item);
	uint32_t index = f_size(fp) / size;		//过滤f_size与item size不对齐的情况
	if(map2_f_update(fp, index, item)){
		return -1;
	}
	return index;
}
/*========================================================================*/
int map2_check_open(map2_t* m, const char* fname){
	if(! map2_f_is_openning(m->file)){
		return 0;
	}
	if(strcmp(m->fname, fname)){
		return 0;
	}
	return 1;
}

const char* map2_setup_path(map2_t* m, const char* fname){
	size_t size = sizeof(m->fpath);
	snprintf(m->fpath, size, ROOT_DIR "/%s/%s", m->name, fname);
	return m->fpath;
}

int map2_open_file(map2_t*m, const char* fname){
	if(map2_check_open(m, fname)){
		return 0;
	}
	map2_f_close(&m->file);
	map2_setup_path(m, fname);
	int ret = map2_f_open(&m->file, m->fpath);
	if(ret){
		memset(m->fname, 0, sizeof(m->fname));
	}
	else{
		strncpy(m->fname, fname, sizeof(m->fname));
	}
	return ret;
}
/*========================================================================*/
#define SES_OP_SORT		"sort"
#define SES_OP_MERGE	"merge"

static void session_path(char* path, size_t size, const char* name){
	snprintf(path, size, ROOT_DIR"/%s/ses.txt", name);
}

static char* session_get_value(FIL* fp, char* val, size_t size){
	if(fgets(val, size, fp) == NULL){
		return NULL;
	}
	int len = strlen(val);
	if(len > 0){
		val[len-1] = 0;
	}
	return val;
}

FIL* session_begin(const char* name, const char* op, int argc, ...){
	char path[32];
	session_path(path, sizeof(path), name);
	FIL* fp = fopen(path, "w+");
	if(!fp){
		return fp;
	}
	va_list p_args;
	va_start(p_args, argc);
	fprintf(fp, "%s\n", op);
	for(int i = 0; i < argc; i++){
		const char* arg = va_arg(p_args, char*);
		fprintf(fp, "%s\n", arg);
	}
	fflush(fp);
	va_end(p_args);
	return fp;
}

void session_finish(const char* name, FIL* fp){
	if(fp){
		fclose(fp);
	}
	char path[32];
	session_path(path, sizeof(path), name);
	remove(path);
}

int session_repair_sort(const char* name, FIL* fp){
	char out[16];
	char in[16];
	if(session_get_value(fp, in, sizeof(in)) == NULL){
		printf("gets in fail\n");
		return 1;
	}

	if(session_get_value(fp, out, sizeof(out)) == NULL){
		printf("gets out fail\n");
		return 1;
	}

	int flag = 0;
	apr_finfo_t finfo;

	if(apr_stat(&finfo, in, 0, gpool) == APR_SUCCESS ){
		flag |= 1;
	}

	if(apr_stat(&finfo, out, 0, gpool) == APR_SUCCESS ){
		flag |= 2;
	}
	if(flag == 3){
		//删除输出
		remove(out);
	}
	return 0;
}

int session_repair_merge(const char* name, FIL* fp){
	char out[16];
	char in1[16];
	char in2[16];
	if(session_get_value(fp, in1, sizeof(in1)) == NULL){
		printf("gets in1 fail\n");
		return 1;
	}
	if(session_get_value(fp, in2, sizeof(in2)) == NULL){
		printf("gets in2 fail\n");
		return 1;
	}
	if(session_get_value(fp, out, sizeof(out)) == NULL){
		printf("read out fail\n");
		return 1;
	}

	int flag = 0;
	apr_finfo_t finfo;
	if(apr_stat(&finfo, in1, 0, gpool) == APR_SUCCESS ){
		flag |= 1;
	}
	if(apr_stat(&finfo, in2, 0, gpool) == APR_SUCCESS ){
		flag |= 2;
	}
	if(apr_stat(&finfo, out, 0, gpool) == APR_SUCCESS ){
		flag |= 4;
	}

	if((flag & 0x03) == 0x03){
		remove(out);
	}
	else{
		if(flag & 0x01){
			remove(in1);
		}
		if(flag & 0x02){
			remove(in2);
		}
	}

	return 0;
}

int session_repair(const char* name){
	char path[32];
	session_path(path, sizeof(path), name);
	FIL* fp = fopen(path, "r");
	if(!fp){
		//没有异常会话
		return 0;
	}
	char buf[32];
	//read op
	if(session_get_value(fp, buf, sizeof(buf)) == NULL){
		printf("read op fail\n");
		fclose(fp);
		remove(path);
		return 0;		
	}

	int ret = 0;
	if(!strcmp(buf, SES_OP_SORT)){
		//repair sort
		ret = session_repair_sort(name, fp);
	}
	else
	if(!strcmp(buf, SES_OP_MERGE)){
		//repair merge
		ret = session_repair_merge(name, fp);
	}
	else{
		printf("unkown op %s\n", buf);
	}
	fclose(fp);
	if(ret >= 0){
		remove(path);
	}

	return ret;
}

/*========================================================================*/

int map2_f_write_valid(FIL* fp, map2_item_t* item){
	if(item->flag){
		uint32_t isize = map2_item_size(item);
		int wlen = fwrite(item, 1, isize, fp);
		if(isize != wlen){
			return -EIO;
		}
	}
	return 0;
}

int map2_do_sort_x_file(FIL* fp, uint8_t *order_buf, uint32_t size){
    //读取待排序文件的数据
	if(f_lseek(fp, 0)){
		return -ENOENT;
	}
	// UINT br = 0;
	// FRESULT res = f_read(fp, order_buf, size, &br);
	// if(res != FR_OK || br != size){
	// 	return -EIO;
	// }
	int rlen = fread(order_buf, 1, size, fp);
	if(rlen != size){
		return -EIO;
	}
    //排序
    map2_item_t* arr = (map2_item_t*)order_buf;
    size_t count = size / map2_item_size(&arr[0]);
    map2_item_sort(arr, count);
	return 0;
}

int map2_sort_x_file_output(const uint8_t* buf, uint32_t size, const char* out_path){
	int ret = 0;
	FIL* fp = fopen(out_path, "w+b");
	if(!fp){
		TRACE_E("open %s fail: %d\n", out_path, errno);
		return -1;
	}

	const map2_item_t* item = (const map2_item_t*)buf;
	uint32_t isize = map2_item_size(item);
	uint32_t off = 0;

	while(off < size){
		item = (const map2_item_t*)(buf + off);
		if(item->flag){
			int wlen = fwrite(item, 1, isize, fp);
			if(isize != wlen){
				ret = -2;
				break;
			}
		}
		off += isize;
	}

	fclose(fp);
	return ret;
}

void map2_get_level_file_path(map2_t* m, uint8_t level, char* path, uint32_t path_size){
	if(m->flags & (1 << level)){
	    snprintf(path, path_size, ROOT_DIR"/%s/%d.MAP", m->name, level * 2 + 1);
	}
	else{
	    snprintf(path, path_size, ROOT_DIR"/%s/%d.MAP", m->name, level * 2);
	}
}

uint8_t map2_get_level_file_num(map2_t* m, uint8_t level){
	uint32_t level_flag = m->order_file_flags >> (level * 2);
	if(level_flag & 1){
		return level * 2 + 1;
	}
	else{
		return level * 2;
	}
}

uint8_t map2_get_level_file_path2(map2_t* m, uint8_t level, char* path, uint32_t path_size){
	uint8_t fnum = map2_get_level_file_num(m, level);
	snprintf(path, path_size, ROOT_DIR"/%s/%d.MAP", m->name, fnum);
	return fnum;
}

int map2_sort_x_file2(map2_t* m){
	FIL* fp = m->file;	
	uint32_t size = f_size(fp);
	uint8_t *order_buf = malloc(size);
	if(!order_buf){
		return -ENOMEM;
	}
	int ret = map2_do_sort_x_file(fp, order_buf, size);
	if(!ret){
		//将排序后的数据写入新的已排序文件
		char path[32];
		uint8_t fnum = map2_get_level_file_path2(m, 0, path, sizeof(path));
		char xpath[32];
    	snprintf(xpath, sizeof(xpath), ROOT_DIR"/%s/" MAP2_X_FILE, m->name);
		FIL* fp = session_begin(m->name, SES_OP_SORT, 2, xpath, path);
		ret = map2_sort_x_file_output(order_buf, size, path);
		if(!ret){
			m->order_file_flags |= 1 << fnum;
			map2_f_close(&m->file);
			remove(xpath);
		}
		else{
			TRACE_E("map2_sort_x_file_output fail: %d\n", ret);
			remove(path);
		}
		session_finish(m->name, fp);
	}
	free(order_buf);
	return ret;
}

int map2_sort_x_file(map2_t* m){
	FIL* fp = m->file;	
	uint32_t size = f_size(fp);
	uint8_t *order_buf = malloc(size);
	if(!order_buf){
		return -ENOMEM;
	}
	int ret = map2_do_sort_x_file(fp, order_buf, size);
	if(!ret){
		//将排序后的数据写入新的已排序文件
		char path[32];
		map2_get_level_file_path(m, 0, path, sizeof(path));
		char xpath[32];
    	snprintf(xpath, sizeof(xpath), ROOT_DIR"/%s/" MAP2_X_FILE, m->name);
		FIL* fp = session_begin(m->name, SES_OP_SORT, 2, xpath, path);
		ret = map2_sort_x_file_output(order_buf, size, path);
		if(!ret){
			m->flags |= 1;
			map2_f_close(&m->file);
			remove(xpath);
		}
		else{
			TRACE_E("map2_sort_x_file_output fail: %d\n", ret);
			remove(path);
		}
		session_finish(m->name, fp);
	}
	free(order_buf);
	return ret;
}

int map2_do_merge_file(map2_t* m, FIL *f1, FIL *f2, FIL *fo){
	uint8_t buf1[64];
	uint8_t buf2[64];
	map2_item_t* item1 = NULL;
	map2_item_t* item2 = NULL;
	uint32_t isize = sizeof(map2_item_t) + m->klen;
	int wlen;
	FRESULT res;
	while(1){
		//读取数据
		if(!item1){
			if(map2_f_get(f1, isize, (map2_item_t*)buf1)){
				break;
			}
			item1 = (map2_item_t*)buf1;
		}
		if(!item2){
			if(map2_f_get(f2, isize, (map2_item_t*)buf2)){
				break;
			}
			item2 = (map2_item_t*)buf2;
		}
		//比较,输出小的项
		map2_item_t* item;
		if(map2_item_cmp(item1, item2) < 0){
			item = item1;
			item1 = NULL;
		}
		else{
			item = item2;
			item2 = NULL;
		}
		
		wlen = fwrite(item, 1, isize, fo);
		if(isize != wlen){
			return -EIO;
		}
	}
	//拷贝f1剩余的数据
	while(!f_eof(f1)){
		if(!item1){
			if(map2_f_get(f1, isize, (map2_item_t*)buf1)){
				break;
			}
			item1 = (map2_item_t*)buf1;
		}

		wlen = fwrite(item1, 1, isize, fo);
		if(isize != wlen){
			return -EIO;
		}
		item1 = NULL;
	}
	//拷贝f2剩余的数据
	while(!f_eof(f2)){
		if(!item2){
			if(map2_f_get(f2, isize, (map2_item_t*)buf2)){
				break;
			}
			item2 = (map2_item_t*)buf2;
		}
		wlen = fwrite(item2, 1, isize, fo);
		if(isize != wlen){
			return -EIO;
		}
		item2 = NULL;
	}
	
	return 0;
}


int map2_merge_file(map2_t* m, const char* path1, const char* path2, const char* path_out){
	FIL* f1 = NULL;
	FIL* f2 = NULL;
	FIL* fo = NULL;
	int ret = 0;

	// if(f_open(&fo, path_out, FA_CREATE_ALWAYS|FA_WRITE|FA_READ) != FR_OK){
	// 	return -EIO;
	// }
	fo = fopen(path_out, "w+b");
	if(!fo){
		return -1;
	}
	if(map2_f_open(&f1, path1)){
		ret = 1;
	}
	if(map2_f_open(&f2, path2)){
		ret = 1;
	}

	if(!ret){
		ret = map2_do_merge_file(m, f1, f2, fo);
	}

	if(f1){
		f_close(f1);
	}

	if(f2){
		f_close(f2);
	}
	
	f_close(fo);
	
	return ret;
}

int map2_merge2(map2_t* m){
	char path1[16];
	char path2[16];
	int level;
	int ret;
	uint32_t flag;

	for(level = 0; level < 16; level++){
		flag = m->order_file_flags >> (level * 2);
		if((flag & 0x03) != 0x03){
			continue;
		}
		snprintf(path1, sizeof(path1), ROOT_DIR"/%s/%d.MAP", m->name, level * 2);
		snprintf(path2, sizeof(path2), ROOT_DIR"/%s/%d.MAP", m->name, level * 2 + 1);
		apr_finfo_t finfo;
		if(apr_stat(&finfo, path1, 0, gpool) == APR_SUCCESS && apr_stat(&finfo, path2, 0, gpool) == APR_SUCCESS){
			//有两个文件
			char path_out[16];
			uint8_t fnum3 = map2_get_level_file_path2(m, level + 1, path_out, sizeof(path_out));
			FIL* fp = session_begin(m->name, SES_OP_MERGE, 3, path1, path2, path_out);
			if(!fp){
				return -1;
			}
			ret = map2_merge_file(m, path1, path2, path_out);
			if(ret){
				remove(path_out);
				session_finish(m->name, fp);
				return ret;
			}
			remove(path1);
			remove(path2);
			session_finish(m->name, fp);

			m->order_file_flags &= ~ (3u << (level * 2));
			m->order_file_flags |= 1u << fnum3;
		}
	}

	return 0;
}

int map2_merge(map2_t* m){
	char path1[16];
	char path2[16];
	int level;
	int ret;
	
	for(level = 0; level < 32; level++){
		if(!(m->flags & (1 << level))){
			continue;
		}
		snprintf(path1, sizeof(path1), ROOT_DIR"/%s/%d.MAP", m->name, level * 2);
		snprintf(path2, sizeof(path2), ROOT_DIR"/%s/%d.MAP", m->name, level * 2 + 1);
		apr_finfo_t finfo;
		if(apr_stat(&finfo, path1, 0, gpool) == APR_SUCCESS && apr_stat(&finfo, path2, 0, gpool) == APR_SUCCESS){
			//有两个文件
			char path_out[16];
			map2_get_level_file_path(m, level + 1, path_out, sizeof(path_out));
			FIL* fp = session_begin(m->name, SES_OP_MERGE, 3, path1, path2, path_out);
			if(!fp){
				return -1;
			}
			ret = map2_merge_file(m, path1, path2, path_out);
			if(ret){
				remove(path_out);
				session_finish(m->name, fp);
				return ret;
			}
			remove(path1);
			remove(path2);
			session_finish(m->name, fp);
			m->flags &= ~ (1u << level);
			m->flags |= 1u << ( level + 1);
		}
	}

	return 0;
}

int f_mkdir(const char* path){
	int ret = apr_dir_make_recursive(path, 0755, gpool);
	if(ret){
		if (ret != EEXIST) {
			// perror("mkdir");
			printf("mkdir error: %d\n", ret);
			return ret;
		}
	}
	return FR_OK;
}
static int map2_setup_flags2(map2_t* m){
    FRESULT res;
	apr_dir_t* dir;
    apr_file_t* thefile;
    apr_finfo_t finfo;
	int ret;
	char path[32];
	m->order_file_flags = 0;
	int fno = 0;
	snprintf(path, sizeof(path), ROOT_DIR "/%s", m->name);
	apr_uint32_t wanted = APR_FINFO_TYPE | APR_FINFO_NAME;
	ret = apr_dir_open(&dir, path, gpool);
	if(ret){
		return -EIO;
	}
	for (;;) {
		ret = apr_dir_read(&finfo, wanted, dir);
		if(ret){
			break;
		}
		if(finfo.filetype == APR_DIR){
			continue;
		}
		
		if(!strcmp(finfo.name, "x.MAP")){
			continue;
		}
		fno = -1;
		sscanf(finfo.name, "%d.MAP", &fno);
		if(fno < 0){
			continue;
		}
		m->order_file_flags |= 1u << fno;
	}
	apr_dir_close(dir);
    return 0;
}
static int map2_setup_flags(map2_t* m){
    FRESULT res;
	apr_dir_t* dir;
    apr_file_t* thefile;
    apr_finfo_t finfo;
	int ret;
    // DIR *dir;
    // FILINFO fno;
	char path[32];
	m->flags = 0;
	snprintf(path, sizeof(path), ROOT_DIR "/%s", m->name);
    // res = f_opendir(&dir, path);                       /* Open the directory */
    // if (res) {
	// 	TRACE_E("%s open fail(%d)", dir, res);
	// 	return -EAGAIN;
    // }
	apr_uint32_t wanted = APR_FINFO_TYPE | APR_FINFO_NAME;
	ret = apr_dir_open(&dir, path, gpool);
	if(ret){
		return -EIO;
	}
	for (;;) {
		// struct dirent* entry = readdir( dir);
		ret = apr_dir_read(&finfo, wanted, dir);
		if(ret){
			break;
		}
		if(finfo.filetype == APR_DIR){
			continue;
		}
//			snprintf(path, sizeof(path), "%s/%s", dir_path, fno.fname);
		// if ((entry->d_type & DT_DIR)) {					  /* It is a directory */
		// 	continue;
		// }
		
		if(!strcmp(finfo.name, "x.MAP")){
			continue;
		}
		int level = -1;
		sscanf(finfo.name, "%d.MAP", &level);
		if(level < 0){
			continue;
		}
		m->flags |= 1 << (level >> 1);
	}
	apr_dir_close(dir);
    return 0;
}

int map2_setup(map2_t* m, const char* name, uint32_t klen){
	FRESULT res;
	char path[32];
	snprintf(path, sizeof(path), ROOT_DIR "/%s", name);
	//创建根文件夹
	res = f_mkdir(path); /* */
	if (res != FR_OK && res != FR_EXIST){
		TRACE_E("create  %s fail: %d\n", path, res);
		return - EAGAIN;
	}
	session_repair(name);
	m->flags = 0;
	strncpy(m->name, name, sizeof(m->name));
	m->klen = klen;
	//初始化map标识
	int ret = map2_setup_flags(m);
	if(!ret){
		//sort
		// char path[32];
    	// snprintf(path, sizeof(path), ROOT_DIR"/%s/" MAP2_X_FILE, m->name);
		// ret = map2_f_open(&m->file, path);
		ret = map2_open_file(m, MAP2_X_FILE);
		if(! ret){
			if(f_size(m->file) >= MAP2_X_MAX_SIZE){
				ret = map2_sort_x_file(m);
			}
		}
	}
	//TODO:启动合并
	if(!ret){
		ret = map2_merge(m);
	}
	return ret;
}

int map2_setup2(map2_t* m, const char* name, uint32_t klen){
	FRESULT res;
	char path[32];
	snprintf(path, sizeof(path), ROOT_DIR "/%s", name);
	//创建根文件夹
	res = f_mkdir(path); /* */
	if (res != FR_OK && res != FR_EXIST){
		TRACE_E("create  %s fail: %d\n", path, res);
		return - EAGAIN;
	}
	session_repair(name);
	strncpy(m->name, name, sizeof(m->name));
	m->klen = klen;
	//初始化map标识
	int ret = map2_setup_flags2(m);
	if(!ret){
		//sort
		ret = map2_open_file(m, MAP2_X_FILE);
		if(! ret){
			if(f_size(m->file) >= MAP2_X_MAX_SIZE){
				ret = map2_sort_x_file2(m);
			}
		}
	}
	//TODO:启动合并
	if(!ret){
		ret = map2_merge2(m);
	}
	return ret;
}

int map2_add2(map2_t* m, const void* key_data, size_t key_size, uint32_t index){
    //1.build item
    uint8_t buf[64];
    map2_item_t* item = map2_item_build_static(buf, key_data, key_size, index);

	if(map2_open_file(m, MAP2_X_FILE)){
		TRACE_E("open [ x ] fail");
		return -EIO;
	}

	if(map2_f_append(m->file, item) < 0){
		TRACE_E("append fail\n");
		return - EIO;
	}

    //3.check if sort
    if(f_size(m->file) < MAP2_X_MAX_SIZE){
		return 0;
    }
	//sort
	if(map2_sort_x_file2(m)){
		TRACE_E("map2_sort_x_file fail\n");
		return -EIO;
	}

    //4.merge
    return map2_merge2(m);
}

int map2_add(map2_t* m, const void* key_data, size_t key_size, uint32_t index){
    //1.build item
    uint8_t buf[64];
    map2_item_t* item = map2_item_build_static(buf, key_data, key_size, index);
    //2.add item to file
    // FIL* fp = m->file;
    // char path[32];
    // snprintf(path, sizeof(path), ROOT_DIR"/%s/" MAP2_X_FILE, m->name);
	// if(map2_f_open(&m->file, path)){
	// 	TRACE_E("open [ %s ] fail", path);
	// 	return - EIO;
	// }
	if(map2_open_file(m, MAP2_X_FILE)){
		TRACE_E("open [ x ] fail");
		return -EIO;
	}

	if(map2_f_append(m->file, item) < 0){
		TRACE_E("append fail\n");
		return - EIO;
	}

    //3.check if sort
    if(f_size(m->file) < MAP2_X_MAX_SIZE){
		return 0;
    }
	//sort
	if(map2_sort_x_file(m)){
		TRACE_E("map2_sort_x_file fail\n");
		return -EIO;
	}

    //4.merge
    return map2_merge(m);
}
/*====================================================================================================*/
#define SEARCH_RESULT(_file,  _pos)		(((_file) << 24) | (_pos))
#define SEARCH_RES_FILE(_res)			(((_res) >> 24) & 0xFF)
#define SEARCH_RES_POS(_res)			((_res) & 0xFFFFFF)

int map2_check(FIL*fp, int pos, const void* key, uint8_t klen, map2_item_t* item ){
	int size = sizeof(map2_item_t);
	size += klen;

	if(map2_f_read(fp, pos, size, item)){
		return -1;
	}

	int result = memcmp(item->kval, key, klen);
	if (result == 0) {
		return 0;
	}

	return 1;
}

//顺序查找

int map2_seq_search2(map2_t* m, FIL*fp, int pos, const void* key, map2_item_t* item){
	int size = sizeof(map2_item_t);
	size += m->klen;
	int n = f_size(fp) / size;
	int i ;

	for(i = pos; i < n; i++) {
		
		if(map2_f_read(fp, i, size, item)){
			return -1;
		}

		int result = memcmp(item->kval, key, m->klen);
		if (result == 0) {
			return i;
		}
	}

	return -1;	
}
//二分查找

int map2_binary_search2(map2_t* m, FIL*fp, const void* key, map2_item_t* item){
	int low = 0;
	int size = sizeof(map2_item_t);
	size += m->klen;
	int n = f_size(fp) / size;
	int high = n - 1;
	while (low <= high) {
		int mid = (low + high) / 2;
		if(map2_f_read(fp, mid, size, item)){
			return -1;
		}
		int result = memcmp(item->kval, key, m->klen);
		if (result == 0) {
			return mid;
		} else if (result < 0) {
			low = mid + 1;
		} else {
			high = mid - 1;
		}
	}
	return -1;
}

int map2_search_file(map2_t* m, const char* fname, int binary, const void* key, map2_item_t* item){
	if(map2_open_file(m, fname)){
		TRACE_E("open [ %s ] fail", fname);
		return - EIO;
	}
	if(binary){
		return map2_binary_search2(m, m->file, key, item);
	}
	else{
		return map2_seq_search2(m, m->file, 0, key, item);
	}
}

int map2_search_order_file(map2_t* m, uint8_t fnum, const void* key, map2_item_t* item){
	if(m->order_file_flags & (1 << fnum)){
		char fname[8];
		snprintf(fname, sizeof(fname), "%d.MAP", fnum);
		return map2_search_file(m, fname, 1, key, item);
	}
	return -1;
}

int map2_search2(map2_t* m, const void* key, map2_item_t* item){
	int ret;
	char fname[8];
	int pos = -1;
	uint32_t file_flag = m->order_file_flags;
	uint8_t fnum = 0;
	while(file_flag){
		uint32_t mask = 1 << fnum;
		if(file_flag & mask){
			snprintf(fname, sizeof(fname), "%d.MAP", fnum);
			pos = map2_search_file(m, fname, 1, key, item);
			if(pos >= 0){
				return pos;
			}
			file_flag &= ~ mask;
		}
		fnum++;
	}

	return map2_search_file(m, MAP2_X_FILE, 0, key, item);
}

int map2_search(map2_t* m, const void* key, map2_item_t* item){
    FRESULT res;
	apr_dir_t* dir;
    apr_file_t* thefile;
    apr_finfo_t finfo;
	FIL*fp = NULL;
	int ret;
	char path[32];
	int pos = -1;

	snprintf(path, sizeof(path), ROOT_DIR "/%s", m->name);
	apr_uint32_t wanted = APR_FINFO_TYPE | APR_FINFO_NAME;
	ret = apr_dir_open(&dir, path, gpool);
	if(ret){
		return -EIO;
	}
	for (;;) {
		ret = apr_dir_read(&finfo, wanted, dir);
		if(ret){
			break;
		}
		if(finfo.filetype == APR_DIR){
			//跳过文件夹
			continue;
		}
		// snprintf(path, sizeof(path), ROOT_DIR "/%s/%s", m->name, finfo.name);
		if(strcmp(finfo.name, "x.MAP")){
			//已排序文件
			pos = map2_search_file(m, finfo.name, 1, key, item);
		}
		else{
			//未排序文件
			pos = map2_search_file(m, finfo.name, 0, key, item);
		}
		if(pos >= 0){
			break;
		}
	}
	apr_dir_close(dir);
    return pos;
}

int map2_delete2(map2_t* m, const void* key){
	uint8_t buf[64];
	map2_item_t* item = (map2_item_t*)buf;
	int pos = map2_search2(m, key, item);
	if(pos < 0){
		return 0;
	}
	return map2_f_delete(m->file, pos, item);
}

int map2_delete(map2_t* m, const void* key){
	uint8_t buf[64];
	map2_item_t* item = (map2_item_t*)buf;
	int pos = map2_search(m, key, item);
	if(pos < 0){
		return 0;
	}
	return map2_f_delete(m->file, pos, item);
}

int binary_search(int array[], int value, int n) {
  int low = 0;
  int high = n - 1;
  while (low <= high) {
    int mid = (low + high) / 2;
    if (array[mid] == value) {
      return mid;
    } else if (array[mid] < value) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  return -1;
}

void test_search(void){
	printf("test_search!\n");
	int array[] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
    int n = sizeof(array) / sizeof(array[0]);
    int value = 1;
    int index = binary_search(array, value, n);
    if (index == -1) {
        printf("not found\n");
    } else {
        printf("found: index = %d, val = %d\n", index, array[index]);
    }
}

/*=============================================================================================*/

static select_item_t * map2_select_item_create(	uint32_t index,	uint8_t flag, int pos, char fnum){
	select_item_t * si = malloc(sizeof(select_item_t));
	si->index = index;
	si->flag = flag;
	si->pos = pos;
	si->fnum = fnum;
	return si;
}

static int map2_result_add_item(select_result_t* result, uint8_t limit, select_item_t* si){
	result->items[result->count] = si;
	result->count++;
	if(result->count == limit){
		return 1;
	}
	return 0;
}


int map2_select_from(map2_t* m, char fnum, select_cond_t* cond, select_result_t* result){
	int ret;
	uint8_t buf[40];
	map2_item_t* item = (map2_item_t*)buf;
	int pos = map2_search_order_file(m, fnum, cond->key, item);
	if(pos < 0){
		return pos;
	}
	if(cond->filter(cond->cond, item)){
		select_item_t* si = map2_select_item_create(item->index, item->flag, pos, fnum);
		ret = map2_result_add_item(result, cond->limit, si);
		if(ret){
			return ret;
		}
	}
	int off;
	//向前查找
	for(off = pos; off > 0; ){
		off--;
		ret = map2_check(m->file, off, cond->key, m->klen, item);
		if(ret < 0){
			break;
		}
		if(ret > 0){
			continue;
		}
		if(cond->filter(cond->cond, item)){
			select_item_t* si = map2_select_item_create(item->index, item->flag, off, fnum);
			ret = map2_result_add_item(result, cond->limit, si);
			if(ret){
				return ret;
			}
		}
	}
	//向后查找
	int size = f_size(m->file);
	int end = size/(sizeof(map2_item_t) + m->klen);
	for(off = pos + 1; off < end; off++){
		ret = map2_check(m->file, off, cond->key, m->klen, item);
		if(ret < 0){
			break;
		}
		if(ret > 0){
			continue;
		}
		if(cond->filter(cond->cond, item)){
			select_item_t* si = map2_select_item_create(item->index, item->flag, off, fnum);
			ret = map2_result_add_item(result, cond->limit, si);
			if(ret){
				return ret;
			}
		}
	}
	return -1;
}

int map2_select_from_sort(map2_t* m, select_cond_t* cond, select_result_t* result){
	uint32_t flag;

	for(int i = 0; i < 16; i++){
		char fnum = i * 2;
		flag = m->order_file_flags >> (uint32_t)fnum;
		if(flag == 0){
			break;
		}
		if(m->order_file_flags & (1u << (uint32_t)fnum)){
			int ret = map2_select_from(m, fnum, cond, result);
			if(ret > 0){
				return ret;
			}
		}
	}

	return -1;
}

int map2_select_from_x(map2_t* m, select_cond_t* cond, select_result_t* result){
	int ret;
	uint8_t buf[40];
	map2_item_t* item = (map2_item_t*)buf;
	//开始查找
	int pos = map2_search_file(m, MAP2_X_FILE, 0, cond->key, item);
	if(pos < 0){
		return pos;
	}

	if(cond->filter(cond->cond, item)){
		select_item_t* si = map2_select_item_create(item->index, item->flag, pos, 'X');
		ret = map2_result_add_item(result, cond->limit, si);
		if(ret){
			return ret;
		}
	}
	//向后查找
	int off, p;
	int size = f_size(m->file);
	int end = size/(sizeof(map2_item_t) + m->klen);
	for(off = pos + 1; off < end; off++){
		p = map2_check(m->file, off, cond->key, m->klen, item);
		if(p < 0){
			break;
		}
		if(p > 0){
			continue;
		}
		if(cond->filter(cond->cond, item)){
			select_item_t* si = map2_select_item_create(item->index, item->flag, off, 'X');
			ret = map2_result_add_item(result, cond->limit, si);
			if(ret){
				return ret;
			}
		}
	}

	return -1;
}

//从map中选取符合条件的项
int map2_select(map2_t* m, select_cond_t* cond, select_result_t* result){
	memset(result, 0, sizeof(*result));
	int ret = map2_select_from_sort(m, cond, result);
	if(ret > 0){
		return 0;
	}
	map2_select_from_x(m, cond, result);
	return 0;
}

int map2_clear(map2_t* m){
	apr_dir_t* dir;
    apr_finfo_t finfo;
	int ret;
	char path[32];
	m->flags = 0;
	m->order_file_flags = 0;
	f_close(m->file);
	snprintf(path, sizeof(path), ROOT_DIR "/%s", m->name);
	apr_uint32_t wanted = APR_FINFO_TYPE | APR_FINFO_NAME;
	ret = apr_dir_open(&dir, path, gpool);
	if(ret){
		return -EIO;
	}
	for (;;) {
		ret = apr_dir_read(&finfo, wanted, dir);
		if(ret){
			break;
		}
		if(finfo.filetype == APR_DIR){
			continue;
		}
		snprintf(path, sizeof(path), ROOT_DIR "/%s/%s", m->name, finfo.name);
		remove(path);
	}
	apr_dir_close(dir);
    return 0;
}

int map2_update(map2_t* m, char fnum, int pos, const void* key, uint32_t index, uint8_t flag){	
	if(fnum < 32){
		char fname[8];
		snprintf(fname, sizeof(fname), "%d.MAP", fnum);
		if(map2_open_file(m, fname)){
			return -EIO;
		}
	}
	else{
		if(map2_open_file(m, MAP2_X_FILE)){
			return -EIO;
		}
	}
	uint8_t buf[40];
	map2_item_t* item = map2_item_build_static(buf, key, m->klen, index);
	item->flag = flag;
	item->check_sum = map2_item_get_check_sum(item);
	return map2_f_write(m->file, pos, item);
}


void map2_select_result_clean(select_result_t* result){
	for(int i = 0; i < result->count; i++){
		free(result->items[i]);
	}
	result->count = 0;
}
